package fun.coding.leetcode;

import java.util.HashSet;
import java.util.Set;

public class LinkedListCycleII {

	public static void main(String[] args) {
		LinkedListCycleII ins = new LinkedListCycleII();
		
		ListNode n1 = new ListNode(1);
		ListNode n2 = new ListNode(2);
		n1.next = n2;
		n2.next = n1;
		
		ListNode t = ins.detectCycle(n1);
		System.out.println(t.val);
	}
	
	public ListNode detectCycle(ListNode head) {
		if (head == null) return null;
		
		ListNode slow = head;
		ListNode fast = head;
		
		while (fast != null) {
			slow = slow.next;
			fast = fast.next;
			
			if (fast == null) return null;
			
			fast = fast.next;
			if (slow == fast) {
				break;
			}
		}
		if (fast == null) return null;
		
		ListNode h = head;
		while (h != slow) {
			h = h.next;
			slow = slow.next;
		}
		
		return h;
	}
	
    public ListNode detectCycleWithSet(ListNode head) {
    	if (head == null) return null;
    	
    	Set<ListNode> s = new HashSet<ListNode>();
    	
    	ListNode cur = head;
    	
    	while (cur != null) {
    		if (s.contains(cur)) {
    			return cur;
    		}
    		
    		s.add(cur);
    		cur = cur.next;
    	}
    	return null;
    }

}
